Selected Topics in Probability (0366-4926-01)
Spring 2021, Tel Aviv University
Location: Online lectures (zoom link) on Thursdays 13-16.
Instructor: Ron Peled.
We will discuss an assortment of topics in probability theory which are not part of the regular curriculum. The precise choice of topics will depend on student preferences as well as the time constraints.
The only prerequisite is the course Probability for Mathematicians. The final grade will be based on the solution of homework problems.
Notices: We will hold a makeup class on Thursday, June 24 from 13:10 to 16:00. This will be the last class of the semester.
There will be no class on May 20, to allow everyone to participate in the Students Probability Day VIII at the Weizmann Institute.
There will be no class on June 10, due to Student's day 2021 at the university.
Suggested topics
Random walks and electrical networks, Galton-Watson trees, The spin O(n) model, the ergodic theorem and the subadditive ergodic theorem, first passage percolation, singularity of Boolean random matrices, noise sensitivity of Boolean functions, mixing times and cutoff, the harmonic explorer, Kakutani's dichotomy, exchangeability, Shannon-McMillan-Breiman theorem, concentration inequalities.
Relevant books and lecture notes
- Antonio Auffinger, Michael Damron and Jack Hanson, 50 years of first passage percolation.
- Amir Dembo, Lecture Notes on Probability Theory.
- Boucheron, Lugosi, Massart, Concentration inequalities: A nonasymptotic theory of independence.
- Rick Durrett, Probability: Theory and Examples.
- Sacha Friedli and Yvan Velenik, Statistical Mechanics of Lattice Systems: a Concrete Mathematical Introduction.
- Christophe Garban and Jeffrey E. Steif, Noise Sensitivity of Boolean Functions and Percolation.
- Geoffrey Grimmett, Probability on Graphs.
- David A. Levin, Yuval Peres and Elizabeth L. Wilmer, Markov Chains and Mixing Times.
- Russell Lyons and Yuval Peres, Probability on Trees and Networks.
- Asaf Nachmias, Planar Maps, Random Walks and Circle Packing.
- Ron Peled and Yinon Spinka, Lectures on the Spin and Loop O(n) Models.
- Yuval Peres, Probability on Trees: An Introductory Climb.
- Sébastien Roch, Modern Discrete Probability. An Essential Toolkit.
- Yvan Velenik, Chapitres Choisis de Théorie des Probabilités.
- Roman Vershynin, High-Dimensional Probability. An Introduction with Applications in Data Science.
- Roman Vershynin, Four lectures on probabilistic methods for data science.
Homework
The homework problems are available here. Problems will be added to this file on a continuous basis during the semester. Please submit homework in English, if possible.
The final grade will be based on the solution of the homework problems. In order to obtain a full grade, 10 homework problems should be solved correctly, with at most 3 problems taken from each topic. Students are allowed to discuss the problems between them but the writing of solutions should be done individually by each student.
The homework should be submitted to the instructor's (physical or digital) mail box by July 15. Write an email to notify the instructor if a physical copy is submitted.
Lectures
- Lecture 1 (4.3): Introduction. Random walks and electrical networks based on Nachmias' book.
Lecture notes.
- Lecture 2 (11.3): Finite and infinite electrical networks (effective resistance, Thomson's principle, Rayleigh's monotonicity law, Dirichlet principle, recurrence/transience) based on Nachmias' book.
Lecture notes.
- Lecture 3 (18.3): Finite and infinite electrical networks (Nash-Williams inequality, recurrence of Z2, method of random paths, transience of Z3) based on Nachmias' book.
Galton-Watson trees (basic survival/extinction criterion, further discussion of sub-critical and super-critical behavior). Partially based on the Lyons-Peres book.
Lecture notes.
- Lecture 4 (8.4): The ergodic theorem (Stationary sequences. Examples: IID sequences, Markov chains, rotation of the circle. Invariant sigma-algebra. Ergodicity in examples. Proof of the Birkhoff ergodic theorem). Based on Durrett's book.
Lecture notes.
- Lecture 5 (22.4): Applications of the ergodic theorem (Rotation of the circle, Benford's law, range of random walk). Statement, example (longest common subsequence) and two steps of the proof of the subadditive ergodic theorem. Based on Durrett's book.
Lecture notes.
- Lecture 6 (29.4): End of proof of the subadditive ergodic theorem. Applications (products of random matrices, age-dependent branching process). Based on Durrett's book.
Lecture notes.
- Lecture 7 (6.5): First-passage percolation (discussion and definition, time constant using subadditive ergodic theorem, limit shape theorem, discussion of variants of the model and predictions). Based on the Auffinger-Damron-Hanson book 50 years of first passage percolation.
Lecture notes.
- Lecture 8 (13.5): Discussion of the predictions and state-of-the-art regarding the fluctuations of first-passage percolation. Detour on the Efron-Stein concentration inequality (the inequality and its applications to the bounded difference inequality and to the variance of the longest common subsequence) and its application to first-passage percolation. Initial discussion of the Falik-Samorodnitsky inequality (to be used to improve the Efron-Stein bound in its application to first-passage percolation). Based on the Auffinger-Damron-Hanson book 50 years of first passage percolation and on the Boucheron-Lugosi-Massart book on concentration inequalities.
Lecture notes.
- Lecture 9 (27.5): The Benjamini-Kalai-Schramm upper bound on the variance of first passage percolation for uniform weights on {a,b} (including a detour into Boolean function theory and a proof of Talagrand's inequality from the Bonami-Beckner inequality). Discussion of total variation distance and a proof of the logarithmic lower bound on the variance for directed last-passage percolation with Gaussian weights.
Based on the Benjamini-Kalai-Schramm paper, the Auffinger-Damron-Hanson book 50 years of first passage percolation and on self notes.
Lecture notes.
- Lecture 10 (3.6): Further discussion of the total variation distance (Pinsker's inequality, comparison with Hellinger distance and total variation distance of Bernoulli vectors). Application to logarithmic lower bound on the variance for first-passage percolation with Bernoulli weights.
Logarithmic lower bound on transversal fluctuations in two dimensions. Discusson of strict convexity of the limit shape and the scaling relation between the exponents of passage-time fluctuations and transversal fluctuations.
Based on self-notes and the Auffinger-Damron-Hanson book 50 years of first passage percolation.
Lecture notes.
- Lecture 11 (17.6): The Ising and spin O(n) models - description of the models, main results and conjectures. Proof of exponential decay of correlations in the high-temperature regime and in one dimension.
Based on Lectures on the Spin and Loop O(n) Models.
Lecture notes.
- Lecture 12 (24.6): The Ising and spin O(n) models, proofs - Proof of long-range order for the Ising model in two and higher dimensions (the Peierls argument). Proof of the absence of long-range order for the continuous-symmetry models (n>=2) in two dimensions (the Mermin-Wagner theorem, including the power-law upper bound on the decay rate). Some ideas from the proof of long-range order for the continuous-symmetry models in three and higher dimensions (the infra-red bound).
Based on Lectures on the Spin and Loop O(n) Models and on self notes.
Lecture notes.